package com.day4.t1;

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    // 生成100条随机字符串
    public static List<String> generateRandomStrings(int count) {
        List<String> result = new ArrayList<>();
        Random random = new Random();
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        for (int i = 0; i < count; i++) {
            // 生成长度为2-6的随机字符串
            int length = random.nextInt(5) + 2;
            StringBuilder sb = new StringBuilder();

            for (int j = 0; j < length; j++) {
                int index = random.nextInt(chars.length());
                sb.append(chars.charAt(index));
            }

            result.add(sb.toString());
        }

        return result;
    }

    // 计算Levenshtein编辑距离
    public static int levenshteinDistance(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // 创建一个二维数组存储子问题的解
        int[][] dp = new int[m + 1][n + 1];

        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 填充dp数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符相同，则不需要编辑操作
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 否则取插入、删除、替换三种操作的最小值加1
                    dp[i][j] = 1 + Math.min(
                            Math.min(dp[i][j - 1],    // 插入
                                    dp[i - 1][j]),   // 删除
                            dp[i - 1][j - 1] // 替换
                    );
                }
            }
        }

        return dp[m][n];
    }

    // 将编辑距离转换为匹配度百分比
    public static double calculateMatchScore(String target, String candidate) {
        if (target == null || candidate == null) {
            return 0.0;
        }

        int distance = levenshteinDistance(target, candidate);
        int maxLength = Math.max(target.length(), candidate.length());

        // 距离越小，匹配度越高；当两个字符串完全相同时，匹配度为100%
        return maxLength == 0 ? 100.0 : (1.0 - (double) distance / maxLength) * 100;
    }

    // 找出匹配度最高的字符串
    public static List<Map.Entry<String, Double>> findBestMatches(List<String> list, String target) {
        Map<String, Double> scores = new HashMap<>();

        for (String str : list) {
            scores.put(str, calculateMatchScore(target, str));
        }

        // 按匹配度降序排序
        return scores.entrySet().stream()
                .sorted(Map.Entry.<String, Double>comparingByValue().reversed())
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        // 生成100条随机字符串
        List<String> stringList = generateRandomStrings(1000);

        // 测试目标字符串
        String target = "AM";
        System.out.println("目标字符串: " + target);

        long startTime = System.nanoTime();
        List<Map.Entry<String, Double>> matches = findBestMatches(stringList, target);        long endTime = System.nanoTime();
        long duration = endTime - startTime;
        System.out.println("Execution time: " + duration / 1_000_000.0 + " ms");

        // 输出前10个匹配度最高的结果
        System.out.println("匹配结果（前10名）:");
        for (int i = 0; i < Math.min(10, matches.size()); i++) {
            Map.Entry<String, Double> entry = matches.get(i);
            System.out.printf("%s: 匹配度 %.2f%%, 编辑距离 %d%n",
                    entry.getKey(),
                    entry.getValue(),
                    levenshteinDistance(target, entry.getKey()));
        }
    }
}
